\chapter{Dynamic Trees}
This section will demonstrate Replay Attack Avoidance ( $\cite{wiki:rep}$ a network attack in which a valid data transmission is maliciously repeated. This is carried out by an adversary who intercepts the data and retransmits it) and how to calculate signatures when the tree is updated i.e. dynamically growing/changing trees.
\newline

In authentication schemes like this the signature has to be updated if any updates are made to the tree otherwise an untrusted distributor may continue using the older version. As a solution proposed in $\cite{kundustructural}$ we can include the timestamp everytime the tree is updated a new signature can include this timestamp. A signature can be regarded as valid only if it includes the latest timestamp, this will invalidate all other previous signatures.
\newline

\textit{Inserting of Nodes}
An insertion of a node can occur at the leaf, root, in between siblings, in between parent-child. Thus in all these cases the RRON,RPON pair of the newly inserted node should be computed randomly between a given interval so that the properties of traversal numbers are preserved. As demonstrated in the considered report $\cite{kundustructural}$ to compute RRON,RPON pairs in all 4 cases:
\begin{enumerate}
	\item Inserting a Leaf node: If z is the new node added to a parent x then p$_z$ must satisfy min(RPON of tree) $<$ p$_x$ $<$ p$_x$ and r$_z$ should be such that r$_x$ $<$ r$_x$ $<$ max(RRON of tree).
	\item Inserting a Root node: If z is the new root node and x be the old root then (acocording to the new situation z will be the parent of x) p$_z$ must satisfy p$_x$ $<$ p$_x$ and r$_z$ should satisfy r$_z$ $<$ r$_x$.
	\item Inserting in between siblings: If x and y were two siblings (x was the left), then adding a node z in between x and y will be such that the conditions p$_x$ $<$ p$_z$ $<$ p$_y$ and r$_x$ $<$ r$_z$ $<$ r$_y$ must be satisfied.
	\item Inserting in between parent and child: If z is a node inserted between parent x and child y then p$_y$ $<$ p$_z$ $<$ p$_x$ and r$_x$ $<$ r$_z$ $<$ r$_y$ should be true.
\end{enumerate}

\textit{Deletion of a node} The deletion of a node will not falsify any traversal properties, hence only a new signature of the new tree should be recomputed.
\newline

\textit{Computation of the signature}: When a tree is updated the timestamp $\tau$ must be included in the signature, thus we can modify the salt to include this information as follows: a)For RSA modify $\omega_T$ to $\mathcal{H}(\tau).\omega_T$ in Eqn (1) and b) For BGLS modify $\omega_T$ to $\mathcal{H}(\tau) + \omega_T$ in Eqn (2). Thus by accommodating these changes we can recompute the signature $\psi_T$ everytime a tree is updated.
\newline

\textit{Complexity}: In the proposed scheme $\cite{kundustructural}$, insertion of a node takes O(1) cost, inserting m nodes cost O(m). Deletion of nodes do not have any cost. In both cases we have to recompute the signature. In case of MHT insertion or deletion of a node costs O(log(n)) as it has to  and that for m nodes cost O(m.log(n)) where n is the number of nodes in the tree.